A database is used in various kinds of applications, and a relational database (RDB) from which logical inconsistency can be excluded has been mainly used in a medium-scale or large-scale system. For example, RDB is used in systems for airplane seat reservation, etc. In this case, by indicating a key item, a target (one target in many cases) can be quickly searched for, or a reservation can be settled, canceled or changed. Furthermore, each airplane has several hundreds seats at most, and thus the number of empty seats of a specific airplane can be determined.
It is known that RDB as described above is suitable for treatment of tabular data, however, it is not suitable for treatment of tree type data (for example, see non-patent document 1).
Furthermore, there exist some applications which are more suitable for the expression based on the tree type than the expression based on the table type. Particularly, XML adopting a tree type data structure as the standard of data for applications of Intranet or Internet has recently prevailed (see non-patent document 2 for the details of XML, for example).
However, treatment of the tree type data structure, for example, search of tree type data generally has a very low efficiency. A first reason for the low efficiency resides in the fact that data exist in distributed nodes at various locations, and thus it is difficult to quickly specify the location at which data exists. In RDB, for example, data of “age” are stored in only an item of “age” of some tables. However, in the tree type data structure, nodes for holding data of “age” are scattered at various locations, and thus it is general that the corresponding data cannot be searched for unless the overall tree type data structure is checked.
A second reason for the low efficiency resides in the fact that it takes much time to express a search result. In order to express a group of nodes hit in the search, the nodes corresponding to descendent nodes of the node of interest must be often expressed. However, the data structure is ad hoc unlike RDBMS, and thus it takes much time to express the descendant nodes.
Therefore, in order to take advantage of RDB prevailing as the database, there have been proposed methods for constructing tree type data in the form of RDB when the tree type data structure is built in the form of a database (see patent document 1, for example). In RDB, data are decomposed and held in a table (tabular form). Therefore, in order to construct the actual tree type data in the form of RDB, it is necessary to pack the tree type data into the table. However, in order to treat various kinds of tree type data structures, data must be individually packed into the table for each structure, and a system design is made. Accordingly, it is a very complicated task to build the system based on RDB.
Furthermore, there has been proposed a method of constructing tree type data, particularly XML data in the form of a database while keeping the data structure thereof. In the case of the tree type data structure, descendent nodes can be subject to one node, and various expressions can be performed. Therefore, the labor of the system design can be greatly reduced. Accordingly, it has been more strongly required to treat the tree structure data by using as a core a technique which can treat a tree structure like XML.
As an approach to the method of constructing XML data in the form of a database while keeping its form, a copy of data written in a tree structure is taken out, and for example in the case of an item “age”, index data for searching for “age” are separately held (for example, see patent document 2). Accordingly, the merit of XML data that an attribute can be added to the data itself can be sufficiently actively used, and the relational structure of the respective items expressed by using tags can be directly stored.
[Patent Document 1] JP-A-2003-248615
[Patent Document 2] JP-A-2001-195406
[Non-patent Document 1] SEC Co., Ltd., “Karearea White Paper”, [online], [searched on Feb. 19, 2004], Internet <URL:http://wwww.sec.co.jp/products/karearea/>
[Non-patent Document 2] W3C, “Extensible Markup Language (XML)) 1.0 (Third Edition)”, [online], Feb. 4, 2004, [searched on Feb. 19, 2004], Internet <URL:http://www.w3.org/TR/2004/REC-xml-20040204/>